#include "../include/time_heap.h"

/// @brief 扩展堆数组容量到1倍
void time_heap::resize() noexcept(0)
{
    // 创建新堆数组
    heap_timer **tmp = new heap_timer *[2 * capacity];
    // 初始化新数组
    for (int i = 0; i < 2 * capacity; i++)
        tmp[i] = NULL;
    if (!tmp)
        throw exception();
    capacity = 2 * capacity;
    // 复制元素
    for (int i = 0; i < cur_size; i++)
        tmp[i] = array[i];
    delete[] array;
    array = tmp;
}

/// @brief 调整目标定时器位置
/// @param timer
void time_heap::adjust_timer(heap_timer *timer)
{
    if (!timer)
        return;

    // 找到目标定时器的位置
    int hole = 0;
    for (; hole < cur_size; hole++)
        if (array[hole] == timer)
            break;

    // 进行下滤，因为其到期时间延长了
    percolate_down(hole);
}

/// @brief 最小堆下虑
/// @note 确保堆数组中以第hole个节点作为根子树拥有最小堆性质
/// @param hole 节点位置
void time_heap::percolate_down(int hole)
{
    heap_timer *tmp = array[hole];
    int child = 0;
    for (; ((hole * 2 + 1) <= (cur_size - 1)); hole = child)
    {
        child = hole * 2 + 1;
        if ((child < (cur_size - 1)) && (array[child + 1]->expire < array[child]->expire))
            ++child;
        if (array[child]->expire < tmp->expire)
            array[hole] = array[child];
        else
            break;
    }
    array[hole] = tmp;
}

/// @brief 获取堆顶定时器
/// @return 定时器
heap_timer *time_heap::top() const
{
    if (empty())
        return NULL;
    return array[0];
}

/// @brief 删除堆顶定时器
void time_heap::pop_timer()
{
    if (empty())
        return;
    if (array[0])
    {
        delete array[0];
        array[0] = array[--cur_size];
        percolate_down(0);
    }
}

/// @brief 堆是否为空
/// @return true/false
bool time_heap::empty() const
{
    return cur_size == 0;
}

/// @brief 添加定时器
/// @param timer 目标定时器
void time_heap::add_timer(heap_timer *timer) noexcept(0)
{
    if (!timer)
        return;
    // 自动扩充
    if (cur_size >= capacity)
        resize();
    // 获取空穴位置并将堆元素数量加1
    int hole = cur_size++;

    int parent = 0;
    // 对从空穴到根节点的路径上的所有节点执行上虑操作
    for (; hole > 0; hole = parent)
    {
        parent = (hole - 1) / 2;
        if (array[parent]->expire <= timer->expire)
            break;
        array[hole] = array[parent];
    }
    array[hole] = timer;
}

/// @brief 删除定时器
/// @param timer 目标定时器
void time_heap::del_timer(heap_timer *timer)
{
    if (!timer)
        return;
    // 假删除
    timer->cb_func = NULL;
}

/// @brief 心搏函数
void time_heap::tick()
{
    heap_timer *tmp = array[0];
    time_t cur = time(NULL);
    // 循环处理堆中到期的定时器
    while (!empty())
    {
        if (!tmp)
            break;
        // 若堆顶定时器未到期
        if (tmp->expire > cur)
            break;
        // 否则执行堆顶定时器中任务
        if (array[0]->cb_func)
            array[0]->cb_func(array[0]->user_data);
        // 将堆顶定时器删除
        pop_timer();
        // 切换下一个
        tmp = array[0];
    }
}
